\documentclass[11pt,a4paper]{article}
\usepackage[dvips]{graphicx}
\usepackage{natbib} 
\begin{document}

\title{Modern Collision Detection and Response Algorithms For
Computer Games: Refinement of the Irrlicht Engine's Algorithms}
\author{Ben Gilbert W0062289}
\date{9 June 2008}
\maketitle
\pagebreak


\section{Introduction}
This report documents a study of the Irrlicht Engine's collision detection
and response algorithms, and attempts to improve their execution time.
This was to be achieved by changes to the algorithms themselves.  In
contrast, the previous report~\cite[]{r1} for this course focused on improving
execution time by improving the compilation methods.  An approximate
50\% improvement was achieved by caching the results of certain ``slow''
calculations.  Other approaches were trialled but they did not result
in an improve to performance. These approaches included: transforming the
main collision detection algorithm from a recursive algorithm to an
iterative loop, changing the maximum recursion depth, and changing the
granuality of the octree used to store the mesh triangles.  These
approaches encompass all of the approaches outlined in~\cite[]{a3}. The
exception was the application of the C++ \verb+inline+ directive to
functions as it was deemed a compiler issue.

\section{Caching of Triangles Mapped to Ellipsoid Space}
Fauerby's~\cite[]{fauerby}algorithm
(discussed in ~\cite[]{a3}) requires all triangles in the mesh that
defines the game setting and used in
collision detection calculations to be mapped to ellipsoid space.
(Ellipsoid space is a defined by the a mapping function
that maps the ellipsoid that defines the collision object to a unit
sphere).  The implementation used by the Irrlicht Engine does not
store result between function calls.  Performance profiling of the
benchmark program (see ~\cite[]{r1}) indicates that the mapping of
triangles amounts to a considerable portion of the execution time.
For a run of one 100 frames, the mapping function
\verb+tranformVect+\verb+(irr::core::vector3d<float>\&)+\verb+ const+
is called 492 million times, has a total execution time of 18.4
seconds and amounts to 22\% of the total execution time.  


If stored copies of the mapped triangles are maintained and retrieved
to avoid recalculation considerable savings can be made in regard to
execution time.  This is true if the following applies: the objects of
interest are of the small set of sizes and the mesh does not change
during game play.  Both of these requirement are typically true in a
first person shooter type game, for which Fauerby's algorithm was
intended.

A simple realisation of caching was implemented.  For this
implementation it was assumed that all objects of interest were of the
same size.  As implementation that could handle a set of object
sizes would be considerably harder to implement but would probably not
provide greater insight into this problem.  The changes were designed
such that the existing function signatures would not be changed.  The following objects were
modified: \verb+COctTreeTriangleSelector+
(\verb+ITriangle+ and \verb+CTriangle+ were
also modified in a trivial manner to allow
\verb+COctTreeTriangleSelector+'s functions to be called
polymorphically), and \verb+CSceneCollisionManager+.  The
modified files have been provided in Appendix~\ref{triangles-files}.
 
The \verb+COctTreeTriangleSelector+ is a class that stores the mesh
triangles in a octree structure.  Each node in the octree structure
stores triangles that exist within the region of space that the node
represents.  The member function \verb+getTriangles+ perform a
broad phase search using an axis aligned bounding box, which is used
by the Irrlicht engine.  This function will find the triangles that
intersect with the bounding box (placed in an array passed by reference).  The ellispsoid space transformation
can be specified in the form of a matrix and passed as a paramter to
this function.  When this is done, each triangle that is placed in the
array will be mapped to ellipsoid space. 

An array was added to each node of the octree structure to store the
mapped triangles.   \verb+applyTransform+ is a function that maps the
unmapped triangles stored in each nodes to ellipsoid space, and stores
the mapped triangle in the new array.  \verb+applyTransform+ is called
before \verb+getTriangles+ is called in the collision detection
routine.  \verb+applyTransform+ tests if the transformation is
the same as the one currently applied.  If this is true, the function
will return, otherwise the function will remap the triangles.  In the
benchmarking program, all the objects are the same size, therefore the
tranformatiuon is always the same except for the first time the
function is called.  Similarly \verb+getTriangles+ will test if the
transformation is the same as the one currently applied.  If this is
true it will retrieve a stored copy of the mapped triangle, otherwise
it will map the triangle. 




\section{Conclusion}



\bibliographystyle{agsm}
\addcontentsline{toc}{chapter}{\bibname}
\bibliography{all}{}

\appendix
\section{Files Modified to Implement Caching of Triangles Mapped to
  Ellipsoide Space}\label{triangles-files}
	
\end{document}
